1. Field of the Invention
The present invention relates to a fast Fourier transform process. For example, this invention is used in a signal analysis of a voice signal or the like, and a modulation/demodulation process for a digital transmission.
In detail, the invention relates to a fast Fourier transform process that performs a fast Fourier transform process or its inverse transform process of variable sampling points to a series of discrete complex number input signals.
2. Description of the Related Art
Up to now, for example, in a signal analysis of a voice signal, a modulation/demodulation process for a digital transmission, or the like, a fast Fourier transform processing device has been used.
As such a fast Fourier transform processing device, for example, a device disclosed in "ISSCC89, Digest, pp166 to 167, 327, THPM12.5: A 200MIPS Single-Chip 1K FFT Processor" is known.
A fast Fourier transform processing device described in this reference literature performs a computing process by means of data paths composed of a 2-port RAM, a twiddle factor ROM, and plural computing elements.
And this device is provided with plural data paths and improves throughput of the internal computation by performing a parallel processing.
This data path is provided with a pipeline structure composed of a multiplier and an adder-subtracter which are disposed between register files, and performs a Fourier transform for transforming inputted complex number data from a time domain to a frequency domain or an inverse Fourier transform for transforming them from a frequency domain to a time domain by means of this pipeline process.
And this data path performs a fast Fourier transform on the basis of an algorithm of radix 4 in case the number of sampling points is 1024, 256,or 64.
However, since a former fast Fourier transform processing device as disclosed in the above-mentioned reference literature has a data path architecture using a fast Fourier transform algorithm of radix 4, it has a disadvantage that although it can perform a fast transform process when the number of sampling points in the fast Fourier transform is the nth power of 4(namely,4.sup.n), it is much deteriorated in processing efficiency if the number of sampling points is not 4.sup.n.
For example, if the number of sampling points is 512 (the 4th power of 4.times.2) or 128 (the 3rd power of 4.times.2), although it can perform a fast Fourier transform process itself, its processing speed is very slow since it cannot help but perform a very inefficient process.
And a former fast Fourier transform processing device can perform processing by means of plural devices connected in parallel with one another if its internal working memory is insufficient in capacity. However, in that case, a processing system must be built by adding newly a complex adder-subtracter, a complex multiplier, a working memory, and the like to this device as discrete components, and as a result this causes a disadvantage that the processing device comes to be very large in scale. For example, since the fast Fourier transform processing device disclosed in the above-mentioned reference literature cannot perform by itself a fast Fourier transform in which the number of sampling points is more than 1024, a new system as described above must be built, for example, if the number of sampling points is 2048 or 4096.